package with_algoithm.basic_algoithm;


import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        int[] u = new int[i];
        for (int j = 0; j < u.length; j++) {
            u[j] = sc.nextInt();
        }
        quickSort(u, 0, u.length - 1);
        System.out.println(Arrays.toString(u));
    }

    public static void quickSort(int[] arr, int l, int r) {
//      如果数组只有一个元素，直接返回
        if (l >= r) {
            return;
        }

//      x为坑位（这里选择第数组的第二个值为坑），i代表起始索引，j代表终点索引
        int x = arr[l], i = l - 1, j = r + 1;
//      如果i<j持续填坑
        while (i < j) {
            do {
                ++i;
            } while (arr[i] < x);
            do {
                --j;
            } while (arr[j] > x);

            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        quickSort(arr, l, j);
        quickSort(arr, j + 1, r);

    }
}

